A busca Informada ou Heurística utiliza conhecimento de um problema específico além da definição do problema em si e pode encontrar soluções de forma mais eficiente do que uma busca cega.
Existem três estrátegias de busca informada que são: Busca gulosa de melhor escolha, busca A* (pronuncia-se A estrela) e limitada pela memória.
A busca gulosa de melhor escolha tenta expandir o nó que está mais próximo do objetivo, com o fundamento de que isso pode conduzir a uma solução rapidamente. Assim, ela avalia os nós usando apenas a função heurística, ou seja, f(n) = h(n).
A busca A* avalia os nós através da combinação de g(n), o custo para alcançar o nó, e h(n), o custo para ir do nó ao objetivo: f(n) = g(n) + h(n). Uma vez que g(n) dá o custo do caminho desde o nó inicial até o nó n e h(n) é o custo estimado do caminho de menor custo de n até o objetivo, teremos f(n) = custo estimado da solução de menor custo através de n.
A maneira mais simples para reduzir os requisitos de memória para A* é adaptar a ideia de aprofundamento iterativo para o contexto de busca heurística, resultando no algoritmo de aprofundamento iterativo A*.